package com.ahpu.lyf.huffmantree;

import java.util.ArrayList;
import java.util.Collections;

public class HuffmanTree {
    public static void main(String[] args) {
        int[] arr={29,7,8,1,3,6,13};
        treeOrder(createHuffmanTree(arr));
    }

    public static Node createHuffmanTree(int[] arr){
        //先将arr的值创建成Node类型并放入list
        ArrayList<Node> nodes = new ArrayList<>();
        for (int i : arr) {
            nodes.add(new Node(i));
        }
        //对Node的value排序
        Collections.sort(nodes);
//        System.out.println(nodes);
        //循环取前两个树构成一个新树
        while (nodes.size()>1){
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            //构造新树
            Node parentNode = new Node(leftNode.getValue() + rightNode.getValue());
            parentNode.setLeftNode(leftNode);
            parentNode.setRightNode(rightNode);
            //移除这两个树并添加新树
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parentNode);
            //排序循环前面几步
//            System.out.println(nodes);
            Collections.sort(nodes);
        }
        //list中最后一个元素就是最终的赫夫曼树
        return nodes.get(0);
    }

    /**
     * 前缀遍历该树
     * @param root 根节点
     */
    public static void treeOrder(Node root){
        if (root!=null) {
            System.out.println("~~~~~~~~~~~~~~~~前序遍历");
            root.preOrder(root);
            System.out.println("~~~~~~~~~~~~~~~~中序遍历");
            root.infixOrder(root);
        }
        else
            System.out.println("空树");
    }

}

/**
 * 节点类，实现Comparable接口来支持排序
 */
class Node implements Comparable<Node>{
    private final Integer value;
    private Node leftNode;
    private Node rightNode;


    /**
     * 前序遍历
     * @param node 当前节点
     */
    public void preOrder(Node node){
        System.out.println(node);
        if (node.leftNode!=null)
            preOrder(node.leftNode);
        if (node.rightNode!=null)
            preOrder(node.rightNode);
    }

    /**
     * 中序遍历
     * @param node 当前节点
     */
    public void infixOrder(Node node){
        if (node.leftNode!=null)
            infixOrder(node.leftNode);
        System.out.println(node);
        if (node.rightNode!=null)
            infixOrder(node.rightNode);
    }

    public Node(Integer value){
        this.value=value;
    }

    @Override
    public String toString() {
        return "Node[" +
                "value=" + value +
                ']';
    }

    /**
     * 从小到大排序
     * @param o 要比较的对象
     * @return 比较的结果
     */
    @Override
    public int compareTo(Node o) {
        return this.value-o.value;
    }

    public Integer getValue() {
        return value;
    }

    public Node getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(Node leftNode) {
        this.leftNode = leftNode;
    }

    public Node getRightNode() {
        return rightNode;
    }

    public void setRightNode(Node rightNode) {
        this.rightNode = rightNode;
    }
}
